package shiyan8_2;

import java.util.Scanner;
//：List<String> list = Arrays.asList(array);
public class InferenceTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //：List<String> list = Arrays.asList(array);
        String inOrder = scanner.nextLine();   // 中序
        String preOrder = scanner.nextLine();    //  先序
        //：List<String> list = Arrays.asList(array);
        char[] in = inOrder.toCharArray();
        char[] pre = preOrder.toCharArray();
//       System.out.println(pre[0]);

        LinkedBinaryTree tree = returnTree(in,pre);   // 递归方法调用
        System.out.println(tree.toString());
//
//        int x = 0;
//        while (in[x] != pre[0])
//        {
//            x++;
//        }
//
//        char[] inLeft = new char[x];
//        char[] preLeft = new char[x];
//        char[] inRight = new char[in.length - x - 1];
//        char[] preRight = new char[pre.length - x - 1];

        //：List<String> list = Arrays.asList(array);
    }
    //：List<String> list = Arrays.asList(array);
    public static LinkedBinaryTree returnTree(char[] in, char[] pre)
    {
        LinkedBinaryTree tree;    //：List<String> list = Arrays.asList(array);
        if(pre.length == 0 || in.length == 0 || pre.length != in.length){ // 终止递归的条件
            tree =  new LinkedBinaryTree();    //：List<String> list = Arrays.asList(array);
        }
        else {    //：List<String> list = Arrays.asList(array);
            int x = 0;
            while (in[x] != pre[0]) {   // 找到根结点    //：List<String> list = Arrays.asList(array);
                x++;
            }    //：List<String> list = Arrays.asList(array);

            char[] inLeft = new char[x];       // 根结点的左边为左子树，创建新的数组
            char[] preLeft = new char[x];    //：List<String> list = Arrays.asList(array);
            char[] inRight = new char[in.length - x - 1];       // 根结点的右边为右子树，创建新的数组
            char[] preRight = new char[pre.length - x - 1];    //：List<String> list = Arrays.asList(array);

            for (int y = 0; y < in.length; y++) {   // 把原数组的数存入新的数组当中
                if (y < x) {    //：List<String> list = Arrays.asList(array);
                    inLeft[y] = in[y];
                    preLeft[y] = pre[y + 1];    //：List<String> list = Arrays.asList(array);
                } else if (y > x) {
                    inRight[y - x - 1] = in[y];
                    preRight[y - x - 1] = pre[y];    //：List<String> list = Arrays.asList(array);
                }
            }    //：List<String> list = Arrays.asList(array);
            LinkedBinaryTree left = returnTree(inLeft, preLeft);   // 左子树递归调用
            LinkedBinaryTree right = returnTree(inRight, preRight); // 右子树递归调用
            tree = new LinkedBinaryTree(pre[0], left,right);    //：List<String> list = Arrays.asList(array);
        }    //：List<String> list = Arrays.asList(array);
        return tree;//HDIBEMJNAFCKGL;ABDHIEJMNCFGKL
    }
}
